611. 有效三角形的个数

Similar Question

leading to the advanced question

Solution Tips

与三叔之和不同, 这里的是不等关系, 所以不能找到明确的 left 和 right 做排除关系

需要找到区间范围

方案一: 双指针

var triangleNumber = function(nums) {
    const n = nums.length;
    nums.sort((a, b) => a - b);
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        let k = i;
        for (let j = i + 1; j < n; ++j) {
            while (k + 1 < n && nums[k + 1] < nums[i] + nums[j]) {
                ++k;
            }
            ans += Math.max(k - j, 0);
        }
    }
    return ans;
};